package seqList;

/**
 * 火车类,是由多个车厢类拼接在一起
 */
public class SingleLinkedList {
    // 当前火车中车厢的节点个数(实际就是具体元素的个数)
    private int size;
    // 当前火车的火车头
    private Node head;

    /**
     * 在火车头部添加元素-添加一个车厢节点
     * @param val
     */
    public void addFirst(int val) {
        // 新建一个车厢节点
        Node node = new Node(val);
        // 判断当前的火车是否为空
        if (head == null) {
            head = node;
        }else {
            // 火车中有节点，要把当前新车厢挂载到火车头部
            node.next = head;
            head = node;
        }
        size ++;
    }

    /**
     * 在单链表的任意一个索引位置插入元素val
     * @param index
     * @param val
     */
    public void addIndex(int index,int val) {
        // 1.合法性
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        // 头插法
        if (index == 0) {
            addFirst(val);
            return;
        }
        // 2.插入元素
        Node node = new Node(val);
        // 需要找到待插入位置的前驱,从头节点开始向后依次走index - 1步
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        // 此时prev指向待插入位置的前驱节点
        node.next = prev.next;
        prev.next = node;
        size ++;
    }
    // 在单链表的尾部插入元素
    public void addLast(int val) {
        addIndex(size,val);
    }

    /**
     * 根据用户输入的index查找对应值
     * @param index
     * @return
     */
    public int get(int index) {
        if(rangeCheck(index)) {
            // index合法
            // 从头节点开始遍历链表，走到index位置
            Node node = head;
            // 规定了node节点走的步数
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node.val;
        }else {
            System.err.println("get index illegal!");
            return -1;
        }
    }

    /**
     * 判断当前链表中是否包含值为val的节点
     * @param val
     * @return
     */
    public boolean contains(int val) {
        for (Node temp = head;temp != null;temp = temp.next) {
            if (temp.val == val) {
                return true;
            }
        }
        return false;
    }

    /**
     * 将单链表中索引为index的节点值改为newVal
     * @param index
     * @param newVal
     * @return 修改前的值
     */
    public int set(int index,int newVal) {
        if (rangeCheck(index)) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            int oldVal = node.val;
            node.val = newVal;
            return oldVal;
        }else {
            System.err.println("set index illegal!");
            return -1;
        }
    }

    public void removeIndex(int index) {
        // 1.判断合法性
        if (rangeCheck(index)) {
            // 2.边界 删除头节点的情况
            if (index == 0) {
                // 删除头节点
                Node temp = head;
                head = head.next;
                temp.next = null;
                size --;
            }else {
                // index中间位置
                // 找到待删除节点的前驱
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                // 待删除节点
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size --;
            }
        }else {
            System.err.println("remove index illegal!");
        }
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }

    public void removeValueOnce(int val) {
        // 遍历链表,找到值为val的节点 -> 不知道值为val的节点在哪个位置
        // 找到后删除(正常的删除都需要找到前驱,只有头节点没前驱)
        if (head != null && head.val == val) {
            // 头节点就是待删除的节点
            Node temp = head;
            head = head.next;
            temp.next = null;
            size --;
        }else {
            // 此时head一定不是待删除的节点
            Node prev = head;
            // 判断前驱的下一个节点值是否等于val
            // 看你取值用的是哪个引用，就判断哪个引用不为空
            while (prev.next != null) {
                // cur就是待删除的节点
                if (prev.next.val == val) {
                    Node cur = prev.next;
                    // 删除cur
                    prev.next = cur.next;
                    cur.next = null;
                    size --;
                    return;
                }
                // prev不是待删除节点的前驱，prev向后移动
                prev = prev.next;
            }
        }
    }

    public void removeValueAll(int val) {
        // 判断头节点是否是待删除节点
        while (head != null && head.val == val) {
            head = head.next;
            size --;
        }
        if (head == null) {
            // 此时链表中的值全是val
            return;
        }else {
            Node prev = head;
            while (prev.next != null) {
                if (prev.next.val == val) {
                    Node cur = prev.next;
                    // 删除cur
                    prev.next = cur.next;
                    cur.next = null;
                    size --;
                }else {
                    prev = prev.next;
                }
            }
        }
    }

    /**
     * 判断用户输入的index是否合法(改，查，删除使用)
     * @param index
     * @return
     */
    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }


    public String toString() {
        String ret = "";
        // 遍历火车这个类，
        // 从火车头(head)走到火车尾部
        // 暂时存储当前头节点地址
        Node node = head;
        while (node != null) {
            ret += node.val;
            ret += "->";
            // 继续访问下一节车厢
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}
/**
 * 火车车厢类,一个车厢只能保存一个元素
 */
class Node {
    // 存储具体数据
    int val;
    // 保存下一个车厢的地址
    Node next;
    public Node(int val) {
        this.val = val;
    }
}